package oj;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LC39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<>();
        LinkedList<Integer> path=new LinkedList<>();
        int n=candidates.length;
        dfs(list,path,0,n,target,candidates);
        return list;

    }
    public void dfs(List<List<Integer>> list, LinkedList<Integer> path,int begin,int len,int target,int[] candidates){
        if(target==0){
            list.add(new ArrayList<>(path));
            return;
        }
        if(target<0){
            return;
        }

        for(int i=begin;i<len;i++){
            path.addLast(candidates[i]);
            dfs(list,path,i,len,target-candidates[i],candidates);
            path.removeLast();
        }
    }
}
